Mi manual de algoritmos/version_maraton_interuniversitaria_2008-2/src/grafos/prim.tex

   1 % Generator: GNU source-highlight, by Lorenzo Bettini, http://www.gnu.org/software/src-highlite
   2
   3 {\ttfamily \raggedright {
   4 \noindent
   5 \mbox{}\textbf{\textcolor{RoyalBlue}{\#include}}\ \texttt{\textcolor{Red}{$<$stdio.h$>$}} \\
   6 \mbox{}\textbf{\textcolor{RoyalBlue}{\#include}}\ \texttt{\textcolor{Red}{$<$string$>$}} \\
   7 \mbox{}\textbf{\textcolor{RoyalBlue}{\#include}}\ \texttt{\textcolor{Red}{$<$set$>$}} \\
   8 \mbox{}\textbf{\textcolor{RoyalBlue}{\#include}}\ \texttt{\textcolor{Red}{$<$vector$>$}} \\
   9 \mbox{}\textbf{\textcolor{RoyalBlue}{\#include}}\ \texttt{\textcolor{Red}{$<$queue$>$}} \\
  10 \mbox{}\textbf{\textcolor{RoyalBlue}{\#include}}\ \texttt{\textcolor{Red}{$<$iostream$>$}} \\
  11 \mbox{}\textbf{\textcolor{RoyalBlue}{\#include}}\ \texttt{\textcolor{Red}{$<$map$>$}} \\
  12 \mbox{} \\
  13 \mbox{}\textbf{\textcolor{Blue}{using}}\ \textbf{\textcolor{Blue}{namespace}}\ std\textcolor{BrickRed}{;} \\
  14 \mbox{} \\
  15 \mbox{}\textbf{\textcolor{Blue}{typedef}}\ string\ node\textcolor{BrickRed}{;} \\
  16 \mbox{}\textbf{\textcolor{Blue}{typedef}}\ pair\textcolor{BrickRed}{$<$}\textcolor{ForestGreen}{double}\textcolor{BrickRed}{,}\ node\textcolor{BrickRed}{$>$}\ edge\textcolor{BrickRed}{;} \\
  17 \mbox{}\textbf{\textcolor{Blue}{typedef}}\ map\textcolor{BrickRed}{$<$}node\textcolor{BrickRed}{,}\ vector\textcolor{BrickRed}{$<$}edge\textcolor{BrickRed}{$>$}\ \textcolor{BrickRed}{$>$}\ graph\textcolor{BrickRed}{;} \\
  18 \mbox{} \\
  19 \mbox{} \\
  20 \mbox{}\textcolor{ForestGreen}{int}\ \textbf{\textcolor{Black}{main}}\textcolor{BrickRed}{()}\textcolor{Red}{\{} \\
  21 \mbox{}\ \ \textcolor{ForestGreen}{double}\ length\textcolor{BrickRed}{;} \\
  22 \mbox{}\ \ \textbf{\textcolor{Blue}{while}}\ \textcolor{BrickRed}{(}cin\ \textcolor{BrickRed}{$>$$>$}\ length\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
  23 \mbox{}\ \ \ \ \textcolor{ForestGreen}{int}\ cities\textcolor{BrickRed}{;} \\
  24 \mbox{}\ \ \ \ cin\ \textcolor{BrickRed}{$>$$>$}\ cities\textcolor{BrickRed}{;} \\
  25 \mbox{}\ \ \ \ graph\ g\textcolor{BrickRed}{;} \\
  26 \mbox{}\ \ \ \ \textbf{\textcolor{Blue}{for}}\ \textcolor{BrickRed}{(}\textcolor{ForestGreen}{int}\ i\textcolor{BrickRed}{=}\textcolor{Purple}{0}\textcolor{BrickRed}{;}\ i\textcolor{BrickRed}{$<$}cities\textcolor{BrickRed}{;}\ \textcolor{BrickRed}{++}i\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
  27 \mbox{}\ \ \ \ \ \ string\ s\textcolor{BrickRed}{;} \\
  28 \mbox{}\ \ \ \ \ \ cin\ \textcolor{BrickRed}{$>$$>$}\ s\textcolor{BrickRed}{;} \\
  29 \mbox{}\ \ \ \ \ \ g\textcolor{BrickRed}{[}s\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{=}\ vector\textcolor{BrickRed}{$<$}edge\textcolor{BrickRed}{$>$();} \\
  30 \mbox{}\ \ \ \ \textcolor{Red}{\}} \\
  31 \mbox{}\ \ \ \ \textcolor{ForestGreen}{int}\ edges\textcolor{BrickRed}{;} \\
  32 \mbox{}\ \ \ \ cin\ \textcolor{BrickRed}{$>$$>$}\ edges\textcolor{BrickRed}{;} \\
  33 \mbox{}\ \ \ \ \textbf{\textcolor{Blue}{for}}\ \textcolor{BrickRed}{(}\textcolor{ForestGreen}{int}\ i\textcolor{BrickRed}{=}\textcolor{Purple}{0}\textcolor{BrickRed}{;}\ i\textcolor{BrickRed}{$<$}edges\textcolor{BrickRed}{;}\ \textcolor{BrickRed}{++}i\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
  34 \mbox{}\ \ \ \ \ \ string\ u\textcolor{BrickRed}{,}\ v\textcolor{BrickRed}{;} \\
  35 \mbox{}\ \ \ \ \ \ \textcolor{ForestGreen}{double}\ w\textcolor{BrickRed}{;} \\
  36 \mbox{}\ \ \ \ \ \ cin\ \textcolor{BrickRed}{$>$$>$}\ u\ \textcolor{BrickRed}{$>$$>$}\ v\ \textcolor{BrickRed}{$>$$>$}\ w\textcolor{BrickRed}{;} \\
  37 \mbox{}\ \ \ \ \ \ g\textcolor{BrickRed}{[}u\textcolor{BrickRed}{].}\textbf{\textcolor{Black}{push$\_$back}}\textcolor{BrickRed}{(}\textbf{\textcolor{Black}{edge}}\textcolor{BrickRed}{(}w\textcolor{BrickRed}{,}\ v\textcolor{BrickRed}{));} \\
  38 \mbox{}\ \ \ \ \ \ g\textcolor{BrickRed}{[}v\textcolor{BrickRed}{].}\textbf{\textcolor{Black}{push$\_$back}}\textcolor{BrickRed}{(}\textbf{\textcolor{Black}{edge}}\textcolor{BrickRed}{(}w\textcolor{BrickRed}{,}\ u\textcolor{BrickRed}{));} \\
  39 \mbox{}\ \ \ \ \textcolor{Red}{\}} \\
  40 \mbox{} \\
  41 \mbox{}\ \ \ \ \textcolor{ForestGreen}{double}\ total\ \textcolor{BrickRed}{=}\ \textcolor{Purple}{0.0}\textcolor{BrickRed}{;} \\
  42 \mbox{}\ \ \ \ priority$\_$queue\textcolor{BrickRed}{$<$}edge\textcolor{BrickRed}{,}\ vector\textcolor{BrickRed}{$<$}edge\textcolor{BrickRed}{$>$,}\ greater\textcolor{BrickRed}{$<$}edge\textcolor{BrickRed}{$>$}\ \textcolor{BrickRed}{$>$}\ q\textcolor{BrickRed}{;} \\
  43 \mbox{}\ \ \ \ q\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{push}}\textcolor{BrickRed}{(}\textbf{\textcolor{Black}{edge}}\textcolor{BrickRed}{(}\textcolor{Purple}{0.0}\textcolor{BrickRed}{,}\ g\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{begin}}\textcolor{BrickRed}{()-$>$}first\textcolor{BrickRed}{));} \\
  44 \mbox{}\ \ \ \ set\textcolor{BrickRed}{$<$}node\textcolor{BrickRed}{$>$}\ visited\textcolor{BrickRed}{;} \\
  45 \mbox{}\ \ \ \ \textbf{\textcolor{Blue}{while}}\ \textcolor{BrickRed}{(}q\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{size}}\textcolor{BrickRed}{())}\textcolor{Red}{\{} \\
  46 \mbox{}\ \ \ \ \ \ node\ u\ \textcolor{BrickRed}{=}\ q\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{top}}\textcolor{BrickRed}{().}second\textcolor{BrickRed}{;} \\
  47 \mbox{}\ \ \ \ \ \ \textcolor{ForestGreen}{double}\ w\ \textcolor{BrickRed}{=}\ q\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{top}}\textcolor{BrickRed}{().}first\textcolor{BrickRed}{;} \\
  48 \mbox{}\ \ \ \ \ \ q\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{pop}}\textcolor{BrickRed}{();}\ \textit{\textcolor{Brown}{//!!}} \\
  49 \mbox{} \\
  50 \mbox{}\ \ \ \ \ \ \textbf{\textcolor{Blue}{if}}\ \textcolor{BrickRed}{(}visited\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{count}}\textcolor{BrickRed}{(}u\textcolor{BrickRed}{))}\ \textbf{\textcolor{Blue}{continue}}\textcolor{BrickRed}{;} \\
  51 \mbox{} \\
  52 \mbox{}\ \ \ \ \ \ visited\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{insert}}\textcolor{BrickRed}{(}u\textcolor{BrickRed}{);} \\
  53 \mbox{}\ \ \ \ \ \ total\ \textcolor{BrickRed}{+=}\ w\textcolor{BrickRed}{;} \\
  54 \mbox{}\ \ \ \ \ \ vector\textcolor{BrickRed}{$<$}edge\textcolor{BrickRed}{$>$}\ \textcolor{BrickRed}{\&}vecinos\ \textcolor{BrickRed}{=}\ g\textcolor{BrickRed}{[}u\textcolor{BrickRed}{];} \\
  55 \mbox{}\ \ \ \ \ \ \textbf{\textcolor{Blue}{for}}\ \textcolor{BrickRed}{(}\textcolor{ForestGreen}{int}\ i\textcolor{BrickRed}{=}\textcolor{Purple}{0}\textcolor{BrickRed}{;}\ i\textcolor{BrickRed}{$<$}vecinos\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{size}}\textcolor{BrickRed}{();}\ \textcolor{BrickRed}{++}i\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
  56 \mbox{}\ \ \ \ \ \ \ \ node\ v\ \textcolor{BrickRed}{=}\ vecinos\textcolor{BrickRed}{[}i\textcolor{BrickRed}{].}second\textcolor{BrickRed}{;} \\
  57 \mbox{}\ \ \ \ \ \ \ \ \textcolor{ForestGreen}{double}\ w$\_$extra\ \textcolor{BrickRed}{=}\ vecinos\textcolor{BrickRed}{[}i\textcolor{BrickRed}{].}first\textcolor{BrickRed}{;} \\
  58 \mbox{}\ \ \ \ \ \ \ \ \textbf{\textcolor{Blue}{if}}\ \textcolor{BrickRed}{(}visited\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{count}}\textcolor{BrickRed}{(}v\textcolor{BrickRed}{)}\ \textcolor{BrickRed}{==}\ \textcolor{Purple}{0}\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
  59 \mbox{}\ \ \ \ \ \ \ \ \ \ q\textcolor{BrickRed}{.}\textbf{\textcolor{Black}{push}}\textcolor{BrickRed}{(}\textbf{\textcolor{Black}{edge}}\textcolor{BrickRed}{(}w$\_$extra\textcolor{BrickRed}{,}\ v\textcolor{BrickRed}{));} \\
  60 \mbox{}\ \ \ \ \ \ \ \ \textcolor{Red}{\}} \\
  61 \mbox{}\ \ \ \ \ \ \textcolor{Red}{\}} \\
  62 \mbox{}\ \ \ \ \textcolor{Red}{\}} \\
  63 \mbox{} \\
  64 \mbox{}\ \ \ \ \textbf{\textcolor{Blue}{if}}\ \textcolor{BrickRed}{(}total\ \textcolor{BrickRed}{$>$}\ length\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
  65 \mbox{}\ \ \ \ \ \ cout\ \textcolor{BrickRed}{$<$$<$}\ \texttt{\textcolor{Red}{"{}Not\ enough\ cable"{}}}\ \textcolor{BrickRed}{$<$$<$}\ endl\textcolor{BrickRed}{;} \\
  66 \mbox{}\ \ \ \ \textcolor{Red}{\}}\textbf{\textcolor{Blue}{else}}\textcolor{Red}{\{} \\
  67 \mbox{}\ \ \ \ \ \ \textbf{\textcolor{Black}{printf}}\textcolor{BrickRed}{(}\texttt{\textcolor{Red}{"{}Need\ \%.1lf\ miles\ of\ cable}}\texttt{\textcolor{CarnationPink}{\textbackslash{}n}}\texttt{\textcolor{Red}{"{}}}\textcolor{BrickRed}{,}\ total\textcolor{BrickRed}{);} \\
  68 \mbox{}\ \ \ \ \textcolor{Red}{\}} \\
  69 \mbox{} \\
  70 \mbox{}\ \ \textcolor{Red}{\}} \\
  71 \mbox{}\ \ \textbf{\textcolor{Blue}{return}}\ \textcolor{Purple}{0}\textcolor{BrickRed}{;} \\
  72 \mbox{}\textcolor{Red}{\}} \\
  73
  74 } \normalfont\normalsize